
#define NULL 0

#define MIN(a, b) (a) < (b) ? (a) : (b)
#define MAX(a, b) (a) > (b) ? (a) : (b)

int largestRectangleArea(int* heights, int heightsSize){
    if (heights == NULL || heightsSize == 0) {
        return 0;
    }
    int area = 0;
    int width = 1;
    int length = heights[0];
    int i;
    int low[heightsSize + 1] = {0};

    for (i = 0; i < heightsSize; i++) {
        length = MAX(length, heights[i]);
        if (i + 1 < heightsSize) {
            low[i] = MIN(heights[i], heights[i + 1]);
        } else {
            low[i] = -1;
        }       
    }
    low[heightsSize] = -1;
    area = MAX(area, length * width);
    length = 0;

    for (width = 2; width <= heightsSize; width++) {        
        for (i = 0; i < heightsSize; i++) {
            if (low[i] == -1) {
                break;
            }
            length = MAX(length, low[i]);
            low[i] = MIN(low[i], low[i + 1]);
        }
        area = MAX(area, length * width);
        length = 0;
    }
    return area;
}

int main() {
    int a;
    a = 0;
    return a;
}